package dp

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnq4km/
// https://leetcode-cn.com/problems/house-robber/
// 抢劫房屋，不能抢两个连续的房子
// 算法: 动态规划
// f[i] = max(f[i-1], f[i-2] + num[i])
// 不用担心前一个房子有没有被抢的问题：如果没被抢，那么 f[i-1] == f[i-2] 最后算出来的答案也是正确的
// 时间复杂度: O(n)
func Rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}

	dpArr := make([]int, len(nums))
	dpArr[0] = nums[0]
	dpArr[1] = max(nums[0], nums[1])
	for index := 2; index < len(nums); index++ {
		dpArr[index] = max(dpArr[index-1], dpArr[index-2]+nums[index])
	}
	return dpArr[len(nums)-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
